package top.fengleifeng.总结.线段树;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.总结.线段树
 * @Description:
 * @date Date : 2021年03月24日 5:24 下午
 */
public class SegmentTree {

    private int MAIN;
    /**
     * 原数组
     */
    private int[] arr;

    /**
     * 线段树数组
     */
    private int[] sum;

    /**
     * 延迟新增数据数组
     */
    private int[] lazy;

    /**
     * 修改数据数组
     */
    private int[] change;
    /**
     * 懒更新标志
     */
    private boolean[] update;

    public SegmentTree(int[] origin) {
        MAIN = origin.length + 1;//长度，数组0位置不用
        arr = new int[MAIN];
        for (int i = 1; i <= origin.length; i++) {
            arr[i] = origin[i - 1];
        }
        sum = new int[MAIN << 2];//某一个范围的累加信息
        lazy = new int[MAIN << 2];//某一个范围的延迟增加下发的数据
        change = new int[MAIN << 2];//某一个范围延迟变更下发的数据
        update = new boolean[MAIN << 2];//某一个范围是否需要变更
    }

    //父节点由左右节点相加
    private void pushUp(int rt) {
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }

    /**
     * 初始化 l-r范围内的数据，rt代表这个范围在数组中第几个
     */
    public void build(int l, int r, int rt) {
        if (l == r) {
            sum[rt] = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, rt << 1);
        build(mid + 1, r, rt << 1 | 1);
        pushUp(rt);
    }

    /*
     * L-R代表需要增加的下标，C代表需要增加的值，
     * l-r代表的是下发的任务，rt代表的是当前下发的坐标
     */
    public void add(int L, int R, int C, int l, int r, int rt) {
        //覆盖当前范围，下发范围增加数据
        if (L <= l && R >= r) {
            sum[rt] += C * (r - 1 + l);//r-1+l代表多少个数
            lazy[rt] += C;
            return;
        }
        //当前范围没有覆盖，继续下发
        int mid = (l + r) >> 1;
        //下发前面缓存的lazy数据
        pushDown(rt, mid - l + 1, r - mid);
        //左孩子是否需要下发任务
        if (L <= mid) {
            add(L, R, C, l, mid, rt << 1);
        }
        //右孩子是否需要下发任务
        if (R > mid) {
            add(L, R, C, mid + 1, r, rt << 1 | 1);
        }
        //左右做完任务更新自己
        pushUp(rt);
    }

    public void update(int L, int R, int C, int l, int r, int rt) {
        //覆盖当前范围，下发范围增加数据
        if (L <= l && R >= r) {
            update[rt] = true;
            change[rt] = C;
            sum[rt] = C * (r - 1 + l);//r-1+l代表多少个数
            lazy[rt] = 0;
            return;
        }
        //当前范围没有覆盖，继续下发
        int mid = (1 + r) >> 1;
        //下发前面缓存的lazy数据
        pushDown(rt, mid - l + 1, r - mid);
        //左孩子是否需要下发任务
        if (L <= mid) {
            update(L, R, C, l, mid, rt << 1);
        }
        //右孩子是否需要下发任务
        if (R > mid) {
            update(L, R, C, mid + 1, r, rt << 1 | 1);
        }
        //左右做完更新自己
        pushUp(rt);
    }

    public long query(int L, int R, int l, int r, int rt) {
        //覆盖当前范围，下发范围增加数据
        if (L <= l && R >= r) {
            return sum[rt];
        }
        //当前范围没有覆盖，继续下发
        int mid = (1 + r) >> 1;
        //下发前面缓存的lazy数据
        pushDown(rt, mid - l + 1, r - mid);
        long ans = 0;
        //左孩子是否需要下发任务
        if (L <= mid) {
            ans += query(L, R, l, mid, rt << 1);
        }
        //右孩子是否需要下发任务
        if (R > mid) {
            ans += query(L, R, mid + 1, r, rt << 1 | 1);
        }
        return ans;
    }

    /**
     * @param rt 当前坐标
     * @param ln 左孩子节点个数
     * @param rn 右孩子节点个数
     */
    private void pushDown(int rt, int ln, int rn) {
        if (update[rt]) {
            update[rt << 1] = true;
            update[rt << 1 | 1] = true;
            change[rt << 1] = change[rt];
            change[rt << 1 | 1] = change[rt];
            lazy[rt << 1] = 0;
            lazy[rt << 1 | 1] = 0;
            sum[rt << 1] = change[rt] * ln;
            sum[rt << 1 | 1] = change[rt] * rn;
            update[rt] = false;
        }
        if (lazy[rt] != 0) {
            lazy[rt << 1] += rt;
            sum[rt << 1] += lazy[rt] * ln;
            lazy[rt << 1 | 1] = 0;
            sum[rt << 1 | 1] += lazy[rt] * rn;
            lazy[rt] = 0;
        }
    }

    public static void main(String[] args) {
        int[] ints = {0,1,2,3};
        SegmentTree segmentTree = new SegmentTree(ints);
        segmentTree.build(1,ints.length,1);
        segmentTree.add(1,2,2,1,ints.length,1);
        long query = segmentTree.query(1, 4, 1, ints.length, 1);
        System.out.println(query);
    }

}
